COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.HLINES←  68 	<< 49 NUMBER OF LINES/PAGE >>
C00050 ENDMK
C⊗;
.HLINES←  68 	<< 49 NUMBER OF LINES/PAGE >>
.WCHARS←  48 	<< 81 NUMBER OF CHARS/LINE >>

.turn on "↓#"

.
.
.PAGE FRAME HLINES+2 HIGH WCHARS WIDE 
.AREA TEXTER LINES 1 TO HLINES CHARS 1 TO WCHARS 
.PLACE TEXTER 

.begin verbatim





			 THE BANKRUPTCY OF BASIC

			      John R. Allen

	     The LISP Company Box 487, Redwood Estates 95044
.end


I predict  that  the  current  trends  utilizing
programming languages like BASIC at the  expense
of abstraction will have a serious impact on the
creativity of the next generation of high school
and and college graduates.

I surmise that the  New Mathematics program  met
resistance  because  it  was  too  abstract  and
short-changed intuition.

I believe that computer science has now  matured
to the extent that it can offer an  intermediate
position to the two  above extremes.  I  believe
that this position --based on a few  fundamental
principles of  computation--  can  be  developed
into a  viable and  exciting program  that  will
teach the  substance  of computing  rather  than
dwelling on  the  form of  specific  programming
languages.  These  fundamentals  of  computation
are  easier  to  present  and  understand   than
contemporary programming languages due to  their
pre-occupation with syntax and shortsighted view
of data structures.


The approach  I  am  advocating is  based  on  a
notation/language named  LISP whose  foundations
are  based   on   mathematical   principles   as
well-founded as those of sets and functions, yet
whose programs can  be executed  by a  computer.
Furthermore from a practical standpoint, LISP is
the language  most commonly  used in  Artificial
Intelligence work; these AI applications and the
techniques they embody offer an incredibly  rich
source  of   examples  and   insight  into   the
non-mathematical aspects of computing.


LISP,  with  its   dual  role  as   mathematical
formalism  and  advanced  programming  language,
offers unique  opportunities  to those  who  are
first encountering computing. The point of  this
note is to sketch some of those benefits, and in
the process  show  how  a  language  like  BASIC
shortchanges one's view of computing.


Consider the following quote:

"... it is  important not to  lose sight of  the
fact that there is a difference between training
and  education.   If  computer   science  is   a
fundamental    discipline,    then    university
education  in   this  field   should   emphasize
enduring  fundamental  principles  rather   than
transient current technology."

Peter Wegner Three Computer Cultures, 1970.


The "Three Cultures" referred  to in this  quote
are:  Computer   Mathematics  (applications   in
traditional  mathematics  that  can   profitably
apply  computers);   Computer  Technology   (the
engineering and physical aspects surrounding the
realization of computing devices), and  Computer
Science (the study of computing). It is a useful
separation  of   the  scientific   aspects   and
ramifications of computers.

Computer Technology  is well  understood in  the
Silicon Valley; it this  the art and science  of
building the physical  devices: applied  physics
and engineering.   Computer Mathematics  is  the
art  and   science  of   using  the   tools   in
mathematics:   applied  mathematics.    Computer
Science? It  is the  study of  computation,  and
programming is applied computation!

Returning to  the  body of  the  quotation,  the
necessity to emphasize "fundamental  principles"
is  not   the   sole   responsibility   of   the
universities.  Many of  one's educational  goals
and expectations are established in high school;
it  is  therefore  most  important  that   one's
introduction to any  subject be  as faithful  to
that  discipline  as  teaching  and   technology
allow. Most subject areas have a  well-developed
historical  perspective   that  supports   their
curricula.  Computer  science  is  a  relatively
young field in the technological domain, but its
roots are well-founded in mathematics.

One objective  of this  note is  to  demonstrate
that  an   appropriate  blend   of   traditional
mathematics and  foundational  computing  offers
substantial advantages  for both  programs.  One
concern I have with the current approach is that
both programs may suffer; mathematics may become
(even more) equated with "deep, but irrelevant",
and computing be  equated with  "shallow, but  a
good career". Mathematics  programs have had  to
deal with this phenomenon for years  --dwindling
enrollments in University  programs are  common.
The phenomenon  has even  more drastic  economic
potential in the computing field:  an oft-quoted
statistic for  the useful  lifetime of  computer
science knowledge  is  five  years!  Surely  the
result of teaching technology, not fundamentals.
The result is stagnant engineering or  expensive
retraining to  keep  up.   No  wonder  one  sees
editorials and articles decrying the diminishing
productivity rate in our computing field,  while
pointing  to  Japan's   and  Europe's   superior
performance. Both the French and Japanese have a
strong interest in  foundational computing.   It
is time to turn  things around in this  country,
and the place to begin is in the high schools.

My comments apply  both to  courses that  expect
their attendees to go on to university education
and it applies to programs that are to give  the
general  populace  an   understanding  of   what
computing is  about and  how it  will impact  on
their lives: the important area called "computer
literacy."    In    neither    case    will    a
technology-driven curricula  suffice;  the  next
five  years  will   see  inexpensive   computing
systems  with  the  power  of  today's  research
machines,  tied   together  through   high-speed
networks,   being   accessed   through    highly
interactive   graphical   techniques.    Several
important and innovative  projects are  underway
now to address these issues: the LOGO project at
MIT, the Smalltalk project at Xerox.  A  cursory
knowledge about  how  a computer  works  coupled
with an  introduction  to  BASIC  won't  prepare
people to cope  with these  systems (since  both
systems  are  targeted  as  educational   tools,
perhaps  we   should  expect   to  see   another
"parental backlash" like  that experienced  with
the New Math program).


Further concern is the  effect of inaccurate  or
inadequate information  on  those  who  plan  to
continue in a university.  First, I surmise that
many bright people are put-off by the patch-work
appearance of computing and opt for  disciplines
that show more  substance.  If computer  science
is  to  prosper,   these  individuals  must   be
attracted.  Second,  there are  severe  problems
even for those who  do enter a  computer-related
career. Questions  are  being raised  about  the
"effect of one's first programming language"; it
is a real  concern. The  expressivity and  style
that one develops with their first language  has
long-term  effect.   This  holds   for   natural
language as well as artificial. The lessons that
one  learns  from   BASIC  about  structure   of
algorithms and  data  are hard  to  overcome.  A
colleague of mine  (a professor  at Santa  Clara
University) can give first-hand testimony  about
the difficulties involved in teaching people  to
unlearn  misconceptions  about  computing.   The
department policy has been to use a "structured"
form of Fortran and Pascal as the vehicle.  Both
of these languages support modern techniques for
expressing algorithms.   Those  who  have  BASIC
experience find it difficult to assimilate these
ideas into their programming style while novices
suffer no such handicap.

Please  note:  the  point  is  not  to  teach  a
programming language;  the  point  is  to  teach
about  computing  and,  in  the  process,  teach
people  to  think.   Of  course,  we  need  some
notation for giving precise descriptions of  our
concepts, but the notation should not become the
object of study. Compare:

"Mathematical notation is always introduced  [in
context as needed] rather than being taught,  as
programming  languages   commonly  are,   in   a
separate course. Notation  suited as  a tool  of
thought  in   any  topic   should  permit   easy
introduction in the context of that topic."

Ken Iverson "Notation as a Tool of Thought" 1979
Turing Award Lecture

As  "tools   of   thought",   most   programming
languages  fail  miserably.   Their  design   is
overly constrained by considerations related  to
their execution on contemporary computers; as  a
result they  fall  short in  satisfying  in  the
criteria by which  notations have  traditionally
been judged.

Iverson suggests  that  in the  past,  notations
have succeeded or failed on considerations  like
the following:

Ease  of   expressing  constructs   arising   in
problems

Suggestivity

Ability to subordinate detail

Economy

Amenability to formal proofs

The  first  three  considerations  are  related;
expressions in  the  notation  must  embody  the
problem  statement  in  such  a  way  that   the
intellectual burden in manipulating the notation
is less  than that  involved with  the  informal
conception of the  problem. Manipulation of  the
notation must aid the  solution of the  original
problem as well as support the generalization of
results.


The notion of economy means that one can explain
the principles of the notation from a few  basic
concepts and rules.  For example, number  theory
can be build from  the primitives of the  number
zero,  equality  relation,   the  operation   of
"adding one", and recursion. LISP has a  similar
foundation. Building from the notion of sequence
and equality, with four primitive operations and
recursion one can construct both the theoretical
and the  programming  structures of  LISP.   The
effect is to supply  the learner with a  simple,
easily grasped system that  can be expanded  and
elaborated   as   familiarity   increases.   The
pedagogical benefits  in  such an  approach  are
substantial.

The notion of proof has been a main-stay in  the
history  of  mathematics.   Its  application  in
science  and  parts  of  mathematics  has   been
informal, but  is  always  grounded  on  logical
foundations that would support formal  argument.
A computational  notation must  at least  do  as
well.

To the traditional  notational concerns we  must
add two computer-age ones:

The notation must be executable

The notation  should be  easy for  a machine  to
manipulate

Surely, if the  notation is  to be  usable as  a
programming language it must be implementable on
a machine and the expressions that one writes in
the  notation   must   be   executable   in   an
unambiguous fashion  and must  be computable  in
finite time.

The second point is  overlooked in almost  every
programming language design.   We see  languages
that completely ignore the issue of manipulation
of  programs   (Fortran  and   Algol);  we   see
languages  that   allow  the   manipulation   of
programs as strings (Snobol  and BASIC); we  see
languages that allow  manipulation as  character
arrays (APL).  Yet programs  are none  of  these
objects.  Programs are  structured objects  with
interrelated parts  and  pieces.  Programs  that
manipulate    these    representations     (like
compilers) must  be  able  to  manipulate  these
representations in  meaningful  ways.   To  this
date, LISP is the only notation that supports  a
representation of programs with the  theoretical
benefits  that  allows  mathematical  discussion
while supporting the practical concerns that are
required to write complex programs.


In  summary,   we   must  identify   and   teach
principles of  computation and  in that  context
one must  introduce  a notation.  That  notation
must embody these principles in such a way  that
one can  reason about  statements made  in  that
notation much  like  one  carries  on  sustained
analysis    in     mathematical     disciplines.
Furthermore, that notation must be executable on
a machine in an unambiguous fashion.  We believe
that the underlying  structure of LISP  supplies
such principles.   The  remainder of  this  note
argues this case.


To   begin,   a   useful   distinction   between
mathematics and computer science is: mathematics
stresses "function"  and  and  computer  science
stresses  "algorithm"  --one   can  argue   that
set-theoretic  ideas  are  more  primitive  than
functionality,  but  I  am  not  concerned  with
minimality  arguments.    Regardless  of   one's
starting point, the idea  of "function" is  more
abstract than  the  idea  of  "algorithm".   The
essential  distinction  being  that  a  function
definition gives an (implict or explict) rule of
correspondence  while  an  algorithm  gives   an
explicit computational  method  for  calculating
those correspondences: there are many algorithms
that will compute the same function.  One way to
understand  "functionality"   is   to   view   a
realization of a function as an algorithm.

At the introductory level, moving from  function
to algorithm  can have  substantial benefit.  An
algorithm is  a  concrete recipe  and,  given  a
computer,  one   can  execute   the   algorithm,
reinforcing one's confidence in the process.  It
is important that  introductory concepts have  a
strong intuitive  real-world  component;  later,
one can abstract from  algorithm to function  by
presenting two algorithms that compute the  same
function and explore what that means.


For example, consider  the following example  of
functional notation:

f(x,y) = x*y - 3*x.

When asking "what is  the value of f(1,2)?"   we
note that  it  doesn't  matter  whether  x*y  is
evaluated before  3*x; that  is, f  expresses  a
functional  relationship,   and  any   rule   of
computation    (obeying    certain    precedence
conventions) will  suffice. I  strongly  suspect
that one teaches (and learns) the evaluation  of
such    expressions    algorithmically,     only
abstracting to the functional level much  later,
if ever.

To  motivate  the   function  versus   algorithm
distinction, consider  the  factorial  function,
defined for non-negative integers:

0! = 1

n! = n*(n-1)! if n is greater than 0.

which says, "given a non-negative integer, if it
is zero, the value is 1; otherwise the value  is
that  integer   multiplied  by   the   factorial
function  operating  on  the   integer-minus-1."
or... "given an integer, call it n. If n is zero
the answer expected is 1, otherwise the expected
answer is n multiplied by the factorial function
operating on n-1."

or... combining with functional notation,

.begin verbatim
factorial(n) = if n=0 then 1
		      else n*factorial(n-1)

Now consider:

fun(x,y) = if x=0 then y
		  else fun(x-1,x*y)
.end

take a moment to look  at fun and then  consider
the values of  fun(1,1), fun(2,1) and  fun(3,1),
for example.

Would you like to  conjecture that fun(x,1)  has
the  same  value  as  factorial(x),  for   every
integer x?  How would  you convince  someone  of
that conjecture?  Write  each in  a  programming
notation and  run them  on  a machine  for  many
values of x?  That's certainly a  start: for  if
the conjecture was  false you  might discover  a
mis-match. But that technique is no proof if the
conjecture is true. It requires proof.

Indeed, the equivalence of these definitions can
be proved.  What does this mean? it says we have
two algorithms that  compute the same  function.
The proof technique is essentially  mathematical
induction.  In fact such  proofs are an  elegant
way to  motivate induction,  and a  lot more  of
computing --for the definitions given above  are
called   recursive   definitions,   an   elegant
formalism analogous to our goal/sub-goal problem
solving intuition.

The equations listed above are, in fact, a  form
of  LISP.    In   LISP,   one   uses   recursive
definitions as  programming language  constructs
to  write   elegant  well-structured   programs.
Furthermore, one  can prove  properties of  LISP
programs using mathematically valid  principles.
Finally, one  can combine  the theory  with  the
practice and can write LISP programs that  would
take two definitions  as input,  use the  formal
rules    for    program    manipulation,     and
automatically prove the equivalence of these two
definitions.

It is this last  area, the manipulation of  LISP
programs by  other LISP  programs that  accounts
for much of LISP's power: to be able to  compute
with data one must  represent it in a  computer;
traditionally we  have made  our data  fit  into
numeric  quantities  or  arrays  of  numbers  or
characters.   LISP   frees    us   from    these
restrictions,  allowing  us   to  compute   with
sequences whose elements can be other  sequences
or simply  symbolic names.  Intellectually,  the
shift makes  it  much easier  to  represent  and
manipulate  complex  information;  that  is  the
business   of    Artificial   Intelligence    in
particular, and intelligence in general.

The key to  this flexibility  and liberation  of
thinking was  LISP's  use of  the  sequence  (or
list) as its underlying data representation.  In
LISP, a sequence  is something like  (A, B,  (C,
D)). This sequence has three elements, the third
being a sequence itself.  Since the commas  just
get in the way, we drop them:  (A B (C D)).

For example, to input  the fun algorithm to  our
program-equivalence prover we would write:

.begin verbatim
(DEFINE FUN (X Y)
      (IF (EQ X 0)
	   Y
	  (FUN (MINUS X 1) (TIMES X Y))))
.end


The syntactic transformation from "fun" to "FUN"
is  simple  --essentially  replacing  functional
notations like:
.begin verbatim

f(x, y, g(z))      by     (F X Y (G Z)), but

.end
the transformation is  a powerful  one from  the
perspective of our  prover.  Such programs  must
be able to select, compare, and manipulate  data
structures  that  represent  subexpressions   of
algorithms like "fun".  In the representation, a
subexpression is either an "atomic symbol" or  a
sequence itself; and  any sequence represents  a
functional application, with  the first  element
of the sequence giving  the name of the  applied
function.  Given  this  sequence  representation
and the operations to manipulate sequences,  the
task of  writing complex  programs becomes  much
more manageable.

For   example,    language   processors    (like
interpreters and  compilers)  initially  process
language statements into  an internal  tree-like
representation.  They  do  this  because   these
tree-structures are  an  efficient form  of  the
program for  further processing.   Since  LISP's
sequence notation has  a natural  representation
as a  tree structure  it becomes  quite easy  to
write compilers in LISP.  For example, a  rather
good LISP compiler can be concisely described on
one 8-1/2 x 11 page; can be easily explained and
read; and  can  be proven  correct.   Since  the
transformation is so simple and yet so powerful,
LISP programs are usually expressed directly  in
this sequence  representation  and  executed  in
this form.

Languages that  offer  only  numeric  or  string
objects do not supply sufficient flexibility for
complex processsing of structures; therefore the
programmer     must      create      lower-level
representations   for   the   needed   tree-like
abstractions. The result is a much less readable
and more complex program.

In  BASIC,   this   complexity   permeates   the
programming process.  Consider, for example, the
Towers of  Hanoi  puzzle: given  three  vertical
rods and a stack of  discs on one rod,  arranged
by size such that the largest is on the  bottom;
move the discs to  the adjacent rod, subject  to
the constraints that only one disc may be  moved
at a time, and no disc may be placed on top of a
smaller disc.

Here is a LISP solution.
.begin verbatim
hanoi(n, source, destination, spare) 
  <= if n=1 then move(source, destination)
            else hanoi(n-1, 
		       source, 
	               spare, 
		       destination)
		 move(source, destination)
		 hanoi(n-1, 
		       spare, 
		       destination, 
		       source)
.end
Here is  a BASIC  solution from  the March  1980
issue of BYTE Magazine:

.group skip 46;

.BEGIN VERBATIM

Even translating  the  LISP  solution  into  its
sequence representation,  we still  have a  more
understandable program  than that  displayed  by
BASIC:

(DEFINE HANOI (N SOURCE DESTINATION SPARE)
  (IF (EQ N 1) (MOVE SOURCE DESTINATION)

      (HANOI (SUB1 N) SOURCE SPARE DESTINATION)
      (MOVE SOURCE DESTINATION)
      (HANOI (SUB1 N) SPARE DESTINATION SOURCE)))

with

(DEFINE MOVE (S D)
    (PRINT "Move disk from" S "to" D))

to print the result on the terminal

and a call:

(HANOI 22 "first" "second" third")

to begin execution.
.END

The  solutions  can  be  contrasted  on  several
levels. In  the BASIC  solution, (line  20)  one
must prescribe  the  number of  disks  that  the
program will manipulate;  of course, most  other
programming   languages   also   require    this
declaration.  However,   such   information   is
totally  irrelevant  to  the  description   (and
correctness) of the algorithm; LISP requires  no
such  declarations.   Many  LISP  systems  allow
declarations   to   aid   the   programmer    in
maintaining consistency, and to aid the compiler
when compiling  code,  but the  LISP  definition
will execute quite handily without declarations.

Further criticism can  be raised concerning  the
GOSUB construct.  The  BASIC  program  maintains
that GOSUB 180 is a call on the Hanoi procedure.
That is not at all clear from the text; "180" is
not "Hanoi", and it is  not at all obvious  what
"180"  is  operating  on   as  data.  The   LISP
definition,  with   its  nmeumonic   names   and
explicit  parameters,  makes   it  clear   which
function is  being called  and what  objects  it
operates on.   One  may  also  ponder  what  has
happened to the recursive algorithm when it  was
encoded in the BASIC solution

These last two  issues --  "180" versus  "Hanoi"
and   the   destruction    of   the    recursive
formulation--    exemplify    the    issue    of
"abstraction":  the   abstract,  or   high-level
description of algorithms. The LISP solution  is
more abstract in that it directly expresses  the
relationships between  consecutive steps,  while
not  requiring  unnecessary  specifications   of
implementation details.  Convincing  oneself  of
the correctness  of the  LISP formulation  is  a
much easier task than that of convincing oneself
of the correctness of the BASIC program.


Besides     LISP's     flexible      algorithmic
expressibility, an integral part of LISP's power
derives  from   its   ability  to   define   and
manipulate data abstractly.  This means that one
can write LISP  algorithms that manipulate  data
without regard for the implementation details of
the data.  In LISP one can define and manipulate
"abstract objects". The objects are abstract  in
that they are described  by their behavior,  not
by    their    implementation.    Objects    are
characterized  by  functions  called  "testers",
"selectors", and "constructors". One can test an
object for specified properties; one can  select
components from (appropriately tested)  objects,
and given  a  collection  of  objects,  one  can
create new objects.

These ideas of abstract objects, manipulated  by
algorithms   using   testers,   selectors,   and
constructors,  are  at   the  heart  of   modern
computer science.

Most programming languages have great difficulty
with this  concept  of abstraction.  Either  the
language fails to support an appropriate set  of
component data  types  (Fortran,  Algol,  Basic,
APL) or fails  to support  the interrelating  of
components at  a  high level  (PL/1  and  Pascal
pointers).  The effect  is the  same: one  loses
the    notation    to    the    strictures    of
implementation.


An essential problem stems  from the failure  to
recognize   that   programming   languages   are
essentially notations. As notations, their first
concern  must  be  expressibility  of   thought.
Therefore,  a   high-level  language's   primary
benefit (over  machine language)  is  notational
not computational. The development cycle of most
programming  languages   has  been   driven   by
computational  (implementation)   considerations
rather  than   by   notational   considerations.
Languages  driven  by  implementations   include
Fortran,  Basic,  and  to  some  extent   Algol.
Languages driven by notation include LISP,  APL,
LOGO, and Smalltalk.

So, at one level,  we agree with the  "hands-on"
algorithmic  approach   contained   within   the
computer-oriented  educational  philosophy.  Our
disagreement is not with the instrument, but  in
the way it  is being applied  or "played".   One
objection stems from the emphasis on performance
without an  appropriate view  of the  instrument
itself. The  typical  computing  application  is
exactly   that:   "an   application",   not   an
introduction  to  computing.   The  essence   of
Computing  is  the  study  of  algorithms,   not
applications.  I do  not even advocate  teaching
LISP as a programming  language, per se:  that's
only moving from the  "slide rule" to the  "hand
calculator".

Mechanical techniques, like  the slide rule  (in
mathematics)  and   any   specific   programming
language (in computer science) are inappropriate
vehicles for teaching principles. The slide rule
was only a tool (transient technology), applying
principles   of   mathematics.   A   programming
language is a tool,  applying the principles  of
computing.  It is the fundamental ideas that are
important,  and  those  are  much  more   easily
presented in the  LISP model than  in the  BASIC
model.  As a  "consumer" language,  BASIC is  no
more obnoxious than  Saturday morning  cartoons;
as  a  medium  for  teaching  people  about  the
elegance  of  computing,   it  is  deadly.    It
shortchanges one's  intellect; its  expressivity
and style are extraordinarily primitive. I  fear
we  will  discover  that   we  have  created   a
generation of "consuming  programmers", able  to
read  (execute)  other  people's  programs   but
unable to  write  (create)  effectively  because
they do not understand the principles.

There are several ingredients that contribute to
a  creative  endeavor   besides  an   expressive
language, a  fluent author,  and an  inquisitive
mind. One  must  also have  appropriate  working
conditions.  Though   many   BASIC's   do   have
interactive features, their scope is limited. In
this  area  of  interactive  programming,   LISP
excells.  In  its  role  as  the  implementation
language for  Artificial Intelligence  research,
LISP systems have  acquired an impressive  array
of  program  development  tools.  There  is   an
important practical  lesson  to be  gained  from
using such tools,  much like  the liberation  of
expression   one    feels   on    moving    from
pencil-and-paper to  a  good text  editor.  This
mode of communication with a computer is at  the
heart of the  LOGO/Smalltalk enterprises;  these
tools   aid   substantially   in   making    the
program-creation   process   a   pleasant    and
rewarding experience. The immediate feedback  of
interactive   computing,    coupled   with    an
"economic"  (see  earlier  comments)   notation,
results in a very effective pedagogical tool.

Clearly I  cannot adequately  cover a  topic  as
deep and varied LISP in only a few pages. I have
said little  about the  interactive  development
style and  programming  environments  that  LISP
lends itself to,  and I have  said little  about
the kinds of applications that has made LISP the
major  tool  of  AI.   I  am  preparing  a  more
detailed version of this paper that will address
these issues, however I feel these  foundational
issues  are  the  most   critical.  I  am   most
interested in your reaction  to this draft,  and
hope  some  of  the  ideas  presented  here  are
valuable to you.



Bibliography
1. Iverson, K. "Notation as a Tool of Thought", CACM, August 1980.